package com.coder.algorithm.sort;

/**
 * 归并排序
 * <p>
 * 分成2到多个子序列，每个子序列采用归并排序；将子序列合并成最终排序序列
 *
 * @author yuhushuan
 * @date 2020/6/7 00:25
 */
public class MergeSort implements Sort {
    public MergeSort() {
        System.out.println("归并排序");
    }

    @Override
    public void sort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
//        递归
//        int[] result = new int[array.length];
//        sort_Recursively(array, result, 0, array.length - 1);

//        迭代
        sort_Iteratively(array);
    }

    /**
     * 递归
     *
     * @param array
     * @param result
     * @param start
     * @param end
     */
    private void sort_Recursively(int[] array, int[] result, int start, int end) {
        if (array == null || result == null || array.length != result.length) {
            return;
        }
        if (start < 0 || end >= array.length || start >= end) {
            return;
        }

        int mid = (start + end) >> 1;
        int leftStart = start;
        int leftEnd = mid;
        int rightStart = mid + 1;
        int rightEnd = end;

        sort_Recursively(array, result, leftStart, leftEnd);
        sort_Recursively(array, result, rightStart, rightEnd);

        int index = start;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            result[index++] = array[leftStart] < array[rightStart]
                    ? array[leftStart++] : array[rightStart++];
        }
        while (leftStart <= leftEnd) {
            result[index++] = array[leftStart++];
        }
        while (rightStart <= rightEnd) {
            result[index++] = array[rightStart++];
        }
        for (int i = start; i <= end; ++i) {
            array[i] = result[i];
        }
    }

    /**
     * 迭代
     */
    private void sort_Iteratively(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int len = array.length;
        int[] result = new int[len];
        int block, start;

        // 从每个序列 1 个元素开始合并，直到 block = len;
        for (block = 1; block < 2 * len; block += block) {
            // 相邻两个序列合并，每个序列长度为：block
            for (start = 0; start < len; start += 2 * block) {
                // 两块的起始下标（注意序列不包括结束下标）
                int start1 = start;
                int end1 = Math.min(start + block, len);
                int start2 = end1;
                int end2 = Math.min(start + 2 * block, len);

                //开始对两个block进行归并排序
                int index = start;
                while (start1 < end1 && start2 < end2) {
                    result[index++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
                }
                while (start1 < end1) {
                    result[index++] = array[start1++];
                }
                while (start2 < end2) {
                    result[index++] = array[start2++];
                }
            }

            int[] temp = array;
            array = result;
            result = temp;
        }
    }


}
